1. Field of the Invention
The method relates to a method for mapping on computation engines, in particular arrays, in a run-time approach.
2. Description of the Related Technology
Use of fine- and coarse-grain reconfigurable processing arrays requires the use of placement and routing (P&R) techniques to determine preferable conditions of operation. Specifically, during runtime reconfiguring of the processing array, new locations for processors, or groups of processors treated as a processing unit, must be chosen. Additionally, each processor or block possesses a number of interconnection pins which, when properly connected, permit data interaction between the processing unit. As the number of processing units is increased, or as the processing units are broken into finer-grain segments, the number of possible placement positions increases quickly. Additionally, the possible combinations of routing connections between processing units increase explosively as well.
To determine the preferable location and routing conditions for the processing units, certain algorithms are typically implemented. Several criteria can be evaluated to determine preferable P&R, including, but not limited to, increased processing cost associated with inefficient processor unit tasking or communication cost and delay associated with relaying information to destination processing units resulting in decreased overall efficiency. Some algorithms determine higher-quality locations and connections resulting in faster or more efficient completion of tasks by processing units, usually by increasing the amount of time required to determine the P&R. Faster algorithms typically produce less optimal results for P&R.
Thus, it can be difficult to select and implement an algorithm for P&R during runtime. Time spent selecting P&R for the reconfigurable array increases the eventual total computation cost for the task for which the P&R is necessitated. Accordingly, there is a need for runtime P&R of reconfigurable arrays which selects and implements algorithms that result in more optimal solutions for P&R. Preferably, the optimization is not fixed based on granularity of the processing units, and can be adapted to changing numbers of processing units.